import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-12-18
 * Time: 18:01
 */
public class Pointer {
    //1.零移动
    public static void moveZeroes(int[] nums) {
        int dest = -1,cur = 0;
        while(cur < nums.length) {
            if(nums[cur] == 0) cur++;
            else {
                swap(nums,dest+1,cur);
                dest++;
                cur++;
            }
        }
    }
    private static void swap(int[] nums,int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //2.零复写
    public static void duplicateZeros(int[] arr) {
        int dest = -1,cur = 0;
        int n = arr.length;
        for(; cur < n; cur++) {
            if(arr[cur] == 0) dest += 2;
            else dest++;
            if(dest >= n-1) break;
        }
        if(dest > n-1) {
            arr[dest-1] = 0;
            dest -= 2;
            cur--;
        }
        while(cur >= 0) {
            if(arr[cur] == 0) {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }else {
                arr[dest--] = arr[cur];
            }
            cur--;
        }
    }

    //3.快乐数
    public boolean isHappy(int n) {
        int p1 = n;
        int p2 = hasNext(n);
        while(p1 != p2 ) {
            p1 = hasNext(p1);
            p2 = hasNext(hasNext(p2));
        }
        return p2 == 1;
    }
    private int hasNext(int n) {
        int sum = 0;
        while(n > 0) {
            sum += Math.pow(n % 10,2);
            n /= 10;
        }
        return sum;
    }

    //4.盛最多水的容器
    public int maxArea(int[] height) {
        int left = 0, right = height.length-1;
        int max = 0;
        while(left < right) {
            int v = Math.min(height[left],height[right]) * (right - left);
            max = Math.max(max,v);
            if(height[left] < height[right]) left++;
            else right--;
        }
        return max;
    }

    //5.有效的三角形个数
    public static int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;
        for(int i = n-1; i > 1; i--) {
            int left = 0, right = i-1;
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum > nums[i]) {
                    count = count + right - left;
                    break;
                }
                else left++;
            }
        }
        return count;
    }

    //6.两数之和
    public int[] twoSum(int[] price, int target) {
        int left = 0, right = price.length-1;
        while(left < right) {
            int sum = price[left] + price[right];
            if(sum > target) right--;
            else if(sum < target) left++;
            else return new int[]{price[left],price[right]};
        }
        return new int[]{0};
    }

    //7.三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        //固定一个元素a 在该数后面的区间寻找两个和等于-a
        for(int i = 0; i < nums.length; ) {
            if(nums[i] > 0) return list; //小优化，i下标所在元素的值为非负数时，此时三个数的和不可能为零
            int left = i + 1,right = nums.length-1,target = -nums[i];
            //不停 找到一种情况后不要停下来，继续寻找
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum > target) {
                    right--;
                }else if(sum < target) {
                    left++;
                }else {
                    list.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;
                    right--;
                    //去重 跳过与前一个相同的元素
                    while(left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                }
            }
            //去重 跳过i相同的元素
            i++;
            while(i < nums.length && nums[i] == nums[i-1]) {
                i++;
            }
        }
        return list;
    }

    //8.四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; ) {
            int j = i + 1;
            for(; j < nums.length; ) {
                long aim = (long)target - nums[i] - nums[j];
                int left = j + 1, right = nums.length-1;
                while(left < right) {
                    int sum = nums[left] + nums[right];
                    if(sum > aim) right--;
                    else if(sum < aim) left++;
                    else {
                        list.add(new ArrayList<>
                                (Arrays.asList(nums[i],nums[j],nums[left++],nums[right--])));
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right+1]) right--;
                    }
                }
                j++;
                while(j < nums.length && nums[j] == nums[j-1]) j++;
            }
            i++;
            while(i < nums.length && nums[i] == nums[i-1]) i++;
        }
        return list;
    }
    public static void main(String[] args) {
        /*int[] nums = {1,3,0,0,12};
        moveZeroes(nums);*/
        /*int[] nums = {1,0,2,3,0,4,5,0};
        duplicateZeros(nums);*/
        int[] nums = {4,2,3,4};
    }
}
